<?php

require_once 'table.php';



/**
 * CSVTable
 * 
 * Table implementation using CSV files.
 * 
 * - Insertion: in the end of the file
 * - Deletion:
 *   1. Marking for deletion (by setting id to $idOfDeleted)
 *   2. Sweeping out records marked for the deletion 
 *      (when lots of them accumulated)
 * 
 * @author Kirill Krasnoschekov
 */
class CSVTable extends Table
{
    // IDs set to the deleted records (before removing them completely)
    private static $idOfDeleted = 0;

    // File handler and file last position
    private $fh;
    private $lastPos = 0;
    
    // Indexes loaded into memory
    // array (FieldName1 => array( value1 => array_of_positions,
    //                             value2 => array_of_positions,
    //                             ... ),
    //        ... ,
    //        FieldNameN => array( value1 => array_of_positions,
    //                             value2 => array_of_positions,
    //                             ... ))
    private $indexData;


    
    /**
     * Constructor 
     * 
     * Saves settings, builds indexes, sweeps records marked for deletion.
     * 
     * @author Kirill Krasnoschekov
     */
    public function __construct(array $schema, $name)
    {
        // Saving settings
        parent::__construct($schema, $name);

        // Opening file
        // 'c+' is for reading and writing;
        // old file data is kept;
        // if file doesn't exist, it is created
        $this->fh = fopen($this->name . '.csv', 'c+') or die();
        
        // Building indexes
        // TODO Write and read prepared indexes from files
        $numberOfDeleted = $this->BuildIndexes();
        
        // Empty file?
        $numberOfActual = $this->CountRows();
        if ( $numberOfActual == 0 )
        {
            return True;
        }
        
        // If there are lots of messages marked for deletion - sweep them out
        $c = $numberOfDeleted / $numberOfActual;
        trace("Actual records: {$numberOfActual}. 
            Deleted records: {$numberOfDeleted}. Rate: {$c}");
        if ( $c > 0.3 )
        {
            $this->Sweep();
            $this->BuildIndexes();
        }        
    }

    /**
     * Destructor
     * 
     * @author Kirill Krasnoschekov
     */
    public function __destruct()
    {
        fclose($this->fh);
    }
    
    
    
    /**
     * Does the record with given id exist?
     * 
     * @param int $id
     * @return True/False
     * @author Kirill Krasnoschekov
     */
    public function Exists($id)
    {
        return array_key_exists($id, $this->indexData['id']);
    }
    
    /**
     * Count rows in the table
     * 
     * @return int Number of rows in the table
     * @author Kirill Krasnoschekov
     */
    public function CountRows()
    {
        return count($this->indexData['id']);
    }

    
    
    /**
     * Actually write record to the storage.
     * 
     * Data is recorded as is. No checks, auto-generations and so on.
     * 
     * @param array $data Record in the dictionary form
     * array( FieldName1e => value1 , ... , FieldNameN => valueN)
     * @author Kirill Krasnoschekov
     */
    protected function _Insert(array $data)
    {
        // Writing
        fseek($this->fh, $this->lastPos);
        fputcsv($this->fh, array_values($data));
        
        // Adding the record to indexes
        foreach ( $this->indexes as $fName => $fParam)
        {
            $this->indexData[$fName][ $data[$fName] ][] = $this->lastPos;
        }
        
        traceVar($this->indexData, "Indexes:");
        
        // Saving new last position
        $this->lastPos = ftell($this->fh);
        
        return True;
    }
    
    /**
     * Mark record as deleted.
     * 
     * Records marked for deletion are deleted permanently from time to time
     * by $this->Sweep() method called from the constructor.
     * 
     * @param int $id Id of the record to delete
     * @author Kirill Krasnoschekov
     */
    protected function _Delete($id)
    {
        // How many zeros to write?
        $str = str_repeat('0', ceil(log((integer)$id + 1, 10)));
        
        // Finding position to insert
        $positions = $this->SeekPositions('id', $id);
        traceVar($positions, "Positions found:");

        // Checks:
        // No such record?
        if ( $positions == NULL )
        {
            return False;
        }
        // Record is not unique?
        if ( count($positions) != 1)
        {
            return False;
        }
        $position = $positions[0];
        
        // Writing zeros
        fseek($this->fh, $position);
        fwrite($this->fh, $str);
        
        // Deleting record from indexes
        $this->DeleteFromIndexes($position);

        return True;
    }
    
    /**
     * Fetch items with given conditions.
     * 
     * @param array $cond Dictionary ('fieldName' => 'fieldValue', ...)
     * @param int $start Works like LIMIT first operand
     * @param int $end Works like LIMIT second operand
     * @param boolean $inv Inverse records order?
     * @return array (possibly empty) of records or NULL if error occurs.
     * @author Kirill Krasnoschekov 
     */
    protected function _Select(array $cond, $start, $end, $inv)
    {
        // If no conditions: select all
        if ( count($cond) == 0 ) 
        {
            $set = array();
            foreach ( $this->indexData['id'] as $id => $positions )
            {
                $set = array_merge($set, $positions);
            }
        }
        else 
        {
            // Find positions of records
            foreach ( $cond as $fieldName => $value )
            {
                // If any index item does not exist - the intersection is empty 
                if ( !isset($this->indexData[$fieldName][$value]) )
                {
                    trace("No such id found. Result: empty set.");
                    return array();
                }
                
                $curSet = $this->indexData[$fieldName][$value];
    
                // Calculate intersection
                if ( !isset($set) )
                {
                    $set = $curSet; 
                }
                else 
                {
                    $set = array_intersect($set, $curSet);
                }
                
                traceVar($set, "Condition: {$fieldName} = {$value}");
    
                // If result set is already empty -- no need to search further
                if ( count($set) == 0 )
                {
                    return array();
                }
            }
        }

        // Reverse
        if ( $inv )
        {
            $set = array_reverse($set);
        }

        // Truncate array
        if ( $end != 0 )
        {
            $set = array_slice($set, $start, $end-$start);
        }
        else 
        {
            $set = array_slice($set, $start);
        }
        
        traceVar($set, "Records positions fetched:");
        
        // Fetch records by positions
        $result = array();
        foreach ( $set as $pos )
        {
            $result[] = $this->ParseRow($this->FetchRow($pos));
        }
        
        // Return fetched records
        return $result;
    }
    


    /**
     * Return next key for the record
     * 
     * @return int Next key for the record
     * @author Kirill Krasnoschekov
     */
    protected function GetNextKey()
    {
        trace("Trying to get next key");
        
        // No records in the table yet: returning 1
        if ( count($this->indexData['id']) == 0 )
        {
            return 1;
        }
        
        // Some records exist: finding id next to the maximal
        return max(array_keys($this->indexData['id'])) + 1;
    }
    
    /**
     * Seek in the index for the entry with given value
     * 
     * @param string $indexFieldName Use index built on this field
     * @param mixed $value Search for this value
     * @return array of positions for the records found, or NULL if error occur
     * @author Kirill Krasnoschekov
     */
    protected function SeekPositions($indexFieldName, $value)
    {
        // Does appropriate index exist?
        if ( !array_key_exists($indexFieldName, $this->indexes) )
        {
            // No: returning NULL as error signal
            return NULL;
        }
        
        // Does index contain positions for given value?
        if ( isset($this->indexData[ $indexFieldName ][ $value ]) )
        {
            // Yes: returning array of positions
            return $this->indexData[$indexFieldName][$value];
        }
        else 
        {
            // No: returning empty array
            return array();
        } 
    }
    


    /**
     * Build indexes for fields listed in $indexes property.
     * 
     * @return int Number of records marked for the deletion
     * @author Kirill Krasnoschekov 
     */
    protected function BuildIndexes()
    {
        // (Re)creating index arrays
        foreach ( $this->indexes as $fName => $fParam )
        {
            $this->indexData[$fName] = array();
        }

        // Running through records
        $fieldNames = array_keys($this->schema);
        $pos = 0;
        $numberOfDeleted = 0;
        
        rewind($this->fh);
        while ( $row = fgetcsv($this->fh) )
        {
            // Parsing
            $line = $this->ParseRow($row);
            
            // Skipping records marked for deletion
            if ( (integer) $line['id'] != self::$idOfDeleted )
            {
                // Checking for ID uniqueness
                if ( isset($this->indexData['id'][$line['id']]) )
                {
                    die("Table {$this->name}: 
                        primary key identity violated! (key value: {$line['id']})");
                }
                
                traceVar($line, "Record:");
                
                // Running through fields
                foreach ( $fieldNames as $i => $fieldName )
                {
                    if ( isset($this->indexData[$fieldName]) )
                    {
                        $this->indexData[$fieldName][ $line[$fieldName] ][] = $pos;
                    }
                }
            }
            else 
            {
                // Found record marked for deletion
                $numberOfDeleted++;
            }
            
            // Saving next position
            $pos = ftell($this->fh);
        }
        
        // Saving file last position
        $this->lastPos = $pos;
        
        traceVar($this->indexData, "Indexes");
        
        return $numberOfDeleted;
    }
    
    /**
     * Delete row with given position from all the indexes
     * 
     * @param int $pos
     * @author Kirill Krasnoschekov
     */
    protected function DeleteFromIndexes($pos)
    {
        traceVar($this->indexData, "Index before deleting:");

        /* Complexity:        
         * O(K*N) = O(N)
         * N - number of records in the table
         * K = const - number of index fields
         */
        foreach ( $this->indexes as $fName => $fParam )
        {
            /*
             *  M_k - number of unique values of k-th index
             */
            foreach ( $this->indexData[$fName] as $value => $positions )
            {
                /*
                 * f(i_k) - number of records with i-th value of k-th index
                 * \sum_i f(i_k) = N, k=1,...,K
                 */
                
                // Find elements to remove
                $toUnset = array();
                foreach ( $positions as $i => $position )
                {
                    if ( $position == $pos )
                    {
                        $toUnset[] = $i;
                    }
                }
                
                // Actually remove them from index
                if ( count($toUnset) != 0 )
                {
                    traceVar($this->indexData[$fName][$value], "Positions array 
                        for field {$fName} for value {$value}");
                    traceVar($toUnset, "Unsetting elements with numbers:");
                    foreach ( $toUnset as $key => $i )
                    {
                        unset($this->indexData[$fName][$value][$i]);
                    }
                    traceVar($this->indexData[$fName][$value], "Positions array after deleting:");
                    
                    // If no positions left in index record -- removing it
                    if ( count($this->indexData[$fName][$value]) == 0 )
                    {
                        unset($this->indexData[$fName][$value]);
                    }
                }
            }
        }
        
        traceVar($this->indexData, "Index after deleting:");
    }

    /**
     * Save indexes to the file
     */
    protected function SaveIndexes() 
    {
        // TODO
    }
    
    /**
     * Load indexes from the file
     */ 
    protected function LoadIndexes() 
    {
        // TODO
    }
    
    /**
     * Fetch row with given position from the file
     * 
     * @param $pos Position in the file where the row starts
     * @return array List of values extracted from this line
     * @author Kirill Krasnoschekov
     */
    private function FetchRow($pos)
    {
        fseek($this->fh, $pos);
        return fgetcsv($this->fh);
    }
    
    /**
     * Parse row (in the form of list) to dictionary (fieldName => value)
     * 
     * @param array $row List of values for the record
     * @return array Record in the form of the dictionary
     * @author Kirill Krasnoschekov
     */
    private function ParseRow(array $row)
    {
        // Running through fields
        $record = array();
        foreach ( array_keys($this->schema) as $i => $fieldName )
        {
            $record[$fieldName] = $row[$i];
        }
        
        return $record;
    }
    
    
    /**
     * Sweep the records marked for deletion from the file
     * 
     * Needs to walk through all the file and to rewrite it
     * 
     * @author Kirill Krasnoschekov
     */
    private function Sweep()
    {
        // Temporary file
        $newfh = fopen("{$this->name}.tmp.csv", "w");
        
        // Read the first file line by line
        rewind($this->fh);
        while ( $row = fgetcsv($this->fh) )
        {
            $record = $this->ParseRow($row);
            
            // Skip 'bad' lines
            if ( $record['id'] == 0 )
            {
                continue;
            }
            
            // Write 'good' lines into second file
            fputcsv($newfh, $row); 
        }
        
        // Close all files
        fclose($newfh);
        fclose($this->fh);
        
        // Backup existing file
        unlink("{$this->name}.bak.csv");
        rename("{$this->name}.csv", "{$this->name}.bak.csv");

        // Replace first file by second
        rename("{$this->name}.tmp.csv", "{$this->name}.csv");
        
        // Open main file again
        $this->fh = fopen($this->name . '.csv', 'c+') or die();
    }
}

?>